package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 24 点游戏
 */

public class Code679 {
    public static void main(String[] args) {

    }

    private static final double EPSILON = 1e-6;
    private static final double TARGET = 24.0;

    public boolean judgePoint24(int[] cards) {
        List<Double> nums = new ArrayList<>();
        for (int card : cards) {
            nums.add((double) card);
        }
        return solve(nums);
    }

    private boolean solve(List<Double> nums) {
        if (nums.size() == 1) {
            return Math.abs(nums.get(0) - TARGET) < EPSILON;
        }

        // 选择两个不同的位置
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i != j) {
                    double a = nums.get(i);
                    double b = nums.get(j);

                    // 生成所有可能的运算结果
                    List<Double> results = new ArrayList<>();
                    results.add(a + b);
                    results.add(a - b);
                    results.add(a * b);
                    if (Math.abs(b) > EPSILON) {
                        results.add(a / b);
                    }

                    // 对每个结果递归求解
                    for (double result : results) {
                        List<Double> nextRound = new ArrayList<>();
                        nextRound.add(result);

                        // 添加未选择的数字
                        for (int k = 0; k < nums.size(); k++) {
                            if (k != i && k != j) {
                                nextRound.add(nums.get(k));
                            }
                        }

                        if (solve(nextRound)) {
                            return true;
                        }
                    }
                }
            }
        }

        return false;
    }
}
